﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure
{
    public class Node
    {
        public Node()
        {

        }
        public int data;
        public Node(int value)
        {
            this.data = value;
        }
    }



    public class MyHeap
    {
        int[] heapArray;

        public int[] HeapArray
        {
            get { return heapArray; }
            set { heapArray = value; }
        }
        int currSize = 0;

        public int CurrSize
        {
            get { return currSize; }
            set { currSize = value; }
        }
        int maxSize = 0;
        public MyHeap()
        {

        }
        public MyHeap(int size)
        {
            this.maxSize = size;
            heapArray = new int[size];
            currSize = 0;
        }

        public void HeapSort()
        {
            this.HeapSort(this.heapArray, this.heapArray.Length);
        }

        void HeapSort(int[] A, int HeapSize)
        {
            buildMaxHeap(A, HeapSize);
            for (int i = HeapSize - 1; i > 0; --i)
            {
                int temp = A[0];
                A[0] = A[i];
                A[i] = temp;
                MaxHeapify(A, 0, i - 1);
            }
        }

        void buildMaxHeap(int[] A, int HeapSize)
        {
            for (int i = HeapSize / 2; i >= 0; --i)
            {
                MaxHeapify(A, i, HeapSize);
            }
        }
        public void Sort()
        {

        }

        void MaxHeapify(int[] A, int i, int HeapSize)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;//记录值最大的元素的索引  

            if (left < HeapSize && A[left] > A[i])
            {
                largest = left;
            }

            if (right < HeapSize && A[right] > A[largest])
            {
                largest = right;
            }

            if (largest != i)
            {
                //进行交换  
                int temp = A[i];
                A[i] = A[largest];
                A[largest] = temp;
                MaxHeapify(A, largest, HeapSize);
            }
        }

        public MyHeap(int[] nodes)
        {
            heapArray = new int[nodes.Length];
            Array.Copy(nodes, heapArray, heapArray.Length);
            for (int i = heapArray.Length / 2; i >= 0; --i)
            {
                MaxHeapify(heapArray, i, heapArray.Length);
            }
        }

        public void Remove(Node node)
        {
            // remove top

            // remove other
        }

        public void ShiftUp(int index)
        {
            int parent = (index - 1) / 2;
            int bottom = heapArray[index];
            while ((index > 0) && (heapArray[parent] < bottom))
            {
                heapArray[index] = heapArray[parent];
                index = parent;
                parent = (parent - 1) / 2;
            }
            heapArray[index] = bottom;
        }

        public bool Insert(int newNode)
        {
            if (currSize == maxSize)
                return false;
            //Node newNode = new Node(key);
            heapArray[currSize] = newNode;
            ShiftUp(currSize);
            currSize++;
            return true;
        }

        public int Remove()
        {
            int root = heapArray[0];
            currSize = heapArray.Length;
            currSize--;
            heapArray[0] = heapArray[currSize];
            ShiftDown(0);
            return root;
        }
        /// <summary>
        /// The shiftDown ensures that the root of the heap contains the largest element then its predecessor.
        /// If it is, then its ok otherwise it swap the elements to make it sort and then sends the result 
        /// to the heapsort function
        /// </summary>
        void siftDown(int[] numbers, int root, int bottom)
        {
            int done, maxChild, temp;
            done = 0;
            while ((root * 2 <= bottom) && (done == 0))
            {
                if (root * 2 == bottom)
                    maxChild = root * 2;
                else if (numbers[root * 2] > numbers[root * 2 + 1])
                    maxChild = root * 2;
                else
                    maxChild = root * 2 + 1;

                if (numbers[root] < numbers[maxChild])
                {
                    temp = numbers[root];
                    numbers[root] = numbers[maxChild];
                    numbers[maxChild] = temp;
                    root = maxChild;
                }
                else
                    done = 1;
            }
        }
        public void ShiftDown(int root)
        {
            int largerChild;
            int top = heapArray[root];
            while (root < (int)(currSize / 2))
            {
                int leftChild = 2 * root + 1;
                int rightChild = leftChild + 1;

                if ((rightChild < currSize) && heapArray[leftChild] < heapArray[rightChild])
                    largerChild = rightChild;
                else
                    largerChild = leftChild;
                if (top >= heapArray[largerChild])
                    break;
                heapArray[root] = heapArray[largerChild];
                root = largerChild;
            }
            heapArray[root] = top;
        }

        internal void ShowArray()
        {
            for (int i = 0; i < currSize; i++)
            {
                Console.Write(heapArray[i] + " ");
            }
        }

        internal void IncSize()
        {
            //throw new NotImplementedException();
        }
    }
}
